

#include <sudoku.h>

#include <stdio.h>
#include <stdlib.h>

sudoku *solution;

/**
 * Recursively solve a sudoke using a depth first brute force search algorithm.
 * This can find all possible solutions but will return only the last one 
 * found by default.
 */
sudoku *_sdk_rec_solve(sudoku *sdk){

  /* First try and solve it regularly. */
  if (_sdk_solve(sdk) != NULL){
    //printf("Found a solution:\n");
    //sdk_print_sudoku(sdk);

    if (solution) SDK_FREE_SUDOKU(solution);
    solution = sdk_copy_sudoku(sdk);

    return sdk;

  }
  /* Now make sure that the sudoku is solvable. */
  if (!sdk_solvable(sdk)) return NULL;

  /* Here we now have to recurse. */
  
  // Find a square to recurse on.
  sdk_square *branch = _sdk_find_branch_square(sdk);
  if (branch != NULL){
    //printf("Found branch square...\n");
    //sdk_print_sudoku_square(branch);
  } else {
    printf("Could not find a branch square.\n");
    sdk_print_sudoku(sdk);
    _sdk_print_sudoku_pos_lists(sdk);
    return NULL;
  }
  
  /* For each possibility in the branch square, make a copy. */
  int i = 1;
  for ( ; i <= SDK_WIDTH; i++){

    if (!sdk_llist_contains(branch->pos, i)) continue;
    
    sudoku *tmp = sdk_copy_sudoku(sdk);
    SDK_SET_SQUARE(tmp,(int) branch->row, (int) branch->col, i);
    
    _sdk_rec_solve(tmp);
    SDK_FREE_SUDOKU(tmp);

  }

  return NULL;

}

